Vu Cấm sinh ở Khu Bình quận, Thái Sơn (nay là Thái An, Sơn Đông). Đầu những năm 180, khởi nghĩa Khăn Vàng nổi ra, Vu Cấm ứng theo hịch của triều đình, tự nguyện tòng quân giúp dẹp loạn. Vu Cấm trở thành thuộc hạ của Bào Tín, lúc ấy là Thái thú ở Duyện Châu.

Năm 192, sau khi Tào Tháo cầm quyền ở Duyện Châu, Vu Cấm và quân tình nguyện được phong làm Đô Bá (都伯; chức chỉ huy 100 lính) và đặt dưới sự điều động của Vương Lãng. Vương Lãng thấy Vu Cấm là người bất phàm và có tiềm năng trở thành bậc đại tướng, nên tiến cử Vu Cấm cho Tào Tháo. Tào Tháo phong Vu Cấm làm Tư Mã (司馬) sau khi nói chuyện với Cấm, sau đó điều ông đi đánh Quảng Uy, thuộc Từ Châu, khi đó được cai trị bởi Đào Khiêm. Vu Cấm thành công trong việc chiếm Quảng Uy và được phong làm Hãm Trận Đô Úy (陷陣都尉).